//
// Created by ttao on 2022/7/25.
//

#ifndef COMPUTER_TREE_H
#define COMPUTER_TREE_H

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <assert.h>
#include <malloc.h>
#include <string.h>

#define BOOL    int
#define FALSE   0
#define TRUE    1


#define ISNULL(node) (!node || (void *)node == NULL)
#define ISNOTNULL(node) (!ISNULL(node))

#define isnodeequare(n1, n2) ((ISNULL(n1) || ISNULL(n2))?FALSE:(isequare(n1->key, n2->key)))
#define isequare(s1, s2) ((ISNOTNULL(s1) && ISNOTNULL(s2)) && ((hashcmp(s1, s2) == 0) || s1 == s2)) ? TRUE:FALSE

#define treenodecopy(desn, srcn) desn->spot = srcn->spot;desn->key = srcn->key;desn->color = srcn->color;desn->attr = srcn->attr;
#define treenodenull(desn) desn->spot = NULL;desn->key = NULL;desn->color = 0;desn->attr = 0;
/* ================ start of tree.c ================ */

/*   eg:
        Leader leader1;
        Leader *ld = initLeader(&leader1);
        treenodeadd(ld, "1");
*/

typedef struct Node* noder;
typedef struct Node nod;
#define pnode (*node)

typedef struct{
    noder root_node;  //根节点
} Leader;

struct Spot{
    struct Node* parent;
    struct Node* left;
    struct Node* right;
    void* value;
};
struct Node{
    void *key;
    struct Spot* spot;
    uint8_t attr;   // [root trunck leaf 00000]
    /** RBTREE **/
    uint8_t color;
};

static inline Leader *initLeader(Leader *leader){
    leader->root_node = NULL;
    return leader;
}

#define NODE_ATTR_ISROOT     1
#define NODE_ATTR_ISTRUNCK   2
#define NODE_ATTR_ISLEAF     4
#define NODE_ATTR_MASK       7

// 遍历方式
#define SELECT_NODE_BEFOR  1
#define SELECT_NODE_MIDDLE 2
#define SELECT_NODE_AFTER  3

// 失衡方向
#define NO_BALANCE_LEFT      0b1000000
#define NO_BALANCE_RIGHT     0b0100000

#define NO_BALANCE_P_LEFT    0b0000001
#define NO_BALANCE_P_RIGHT   0b0000100
#define NO_BALANCE_C_LEFT    0b0000010
#define NO_BALANCE_C_RIGHT   0b0001000
#define NO_BALANCE_MASK      0b1111111

static inline void setrootnode(Leader *leader, noder n) {
    leader->root_node = n;
}
static inline noder getrootnode(Leader *leader){
    return leader->root_node;
}
static inline void setnodeisroot(noder node)
/*设置节点为root*/
{
    if (node == NULL) return;
    node->attr |= NODE_ATTR_ISROOT;
    node->attr &= NODE_ATTR_ISTRUNCK ^ NODE_ATTR_MASK;
    node->attr &= NODE_ATTR_ISLEAF ^ NODE_ATTR_MASK;
}

static inline void setnodeisleaf(noder node)
/*设置节点为leaf*/
{
    if (node == NULL) return;
    node->attr &= NODE_ATTR_ISROOT ^ NODE_ATTR_MASK;
    node->attr &= NODE_ATTR_ISTRUNCK ^ NODE_ATTR_MASK;
    node->attr |= NODE_ATTR_ISLEAF;
}

static inline void setnodeistrunk(noder node)
/*设置节点为trunk*/
{
    if(node == NULL) return;
    node->attr &= NODE_ATTR_ISROOT ^ NODE_ATTR_MASK;
    node->attr |= NODE_ATTR_ISTRUNCK;
    node->attr &= NODE_ATTR_ISLEAF ^ NODE_ATTR_MASK;
}

BOOL checknodeattr(noder node, int attr);
BOOL hasBrother(noder node);
noder getBrother(noder node);
BOOL hasChildren(noder node);

noder   gettreebeforenode(noder node);
noder   gettreeafternode(noder node);
void    settreenoderight(Leader *leader,noder node, noder right);
void    settreenodeleft(Leader *leader,noder node, noder left);

noder   treenodenew(void *key,void *value);
void    treenodedestroy(noder node);

void    treenodeadd(Leader *leader, void *key, void *value);
int     treenodedel(Leader *leader, void *key);
noder   treenodesel(Leader *leader, void *key, int type);
int     treenodemodify(Leader *leader, void *key, void *newvalue);

void    treerotatenodeleft(Leader *leader, void *key);
void    treerotatenoderight(Leader *leader, void *key);

int     treenodemaxdeep(noder node);

/* ================ end of tree.c ================ */

/* ================ start of AVL tree.c ================ */

/*
 * eg: NVL树的插入和删除
    Leader leader;
    initLeader(&leader);
    NVLtreenodeadd(&leader, "1");
    NVLtreenodedel(&leader, "1");
 */
void    NVLtreenodedel(Leader *leader, void *key);
void    NVLtreenodeadd(Leader *leader, void *key, void *value);
/* ================ end of AVL tree.c ================ */

/* ================ start of rb tree.c ================ */

/*
 * eg:红黑树
    Leader leader;
    initLeader(&leader);
    RBtreenodeadd(&leader, "1");
    RBtreenodedel(&leader, "1");
 */

#define RBTREE_COLOR_RED    0b00000001
#define RBTREE_COLOR_BLACK  0b00000010

/*红黑树插入时可能的情况*/
#define RBTREE_INSERT_ASPECT_ONE              0b0100000100000000
#define RBTREE_INSERT_ASPECT_TWO              0b0100001000000000
#define RBTREE_INSERT_ASPECT_THREE            0b0100010000000000
#define RBTREE_INSERT_ASPECT_FORE_C_ONE       0b0100100000000001
#define RBTREE_INSERT_ASPECT_FORE_C_TWO       0b0100100000000010
#define RBTREE_INSERT_ASPECT_FIVE_C_ONE       0b0101000000000001
#define RBTREE_INSERT_ASPECT_FIVE_C_TWO       0b0101000000000010

/*红黑树删除时可能的情况*/
#define RBTREE_DEL_ASPECT_ONE                 0b1000000100000000
#define RBTREE_DEL_ASPECT_TWO                 0b1000001000000000
#define RBTREE_DEL_ASPECT_THREE               0b1000010000000000
#define RBTREE_DEL_ASPECT_FORE                0b1000100000000000

#define RBTREE_ASPECT_MASK                    0b1111111111111111


void RBtreenodeadd(Leader *leader, void *key, void *value);
void RBtreenodedel(Leader *leader, void *key);
noder RBtreenodesel(Leader *leader, void *key);

/* ================ end of rb tree.c ================ */

#endif //COMPUTER_TREE_H
